/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年02月16日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        for(int i = 1; i * i <= n; i++){
            dp[i * i] = 1;
        }

        for( int i = 1; i <= n; i++ ){
            for( int j = 1; j*j < i; j++){
                dp[i] = min( dp[i], dp[i - j*j] + 1);
            }
        }

        return dp[n];
    }
};
